/*
Source : https://leetcode.com/problems/range-sum-query-immutable/
Author : nflush@outlook.com
Date   : 2016-08-23
*/
/*
303. Range Sum Query - Immutable

    Total Accepted: 41008
    Total Submissions: 159235
    Difficulty: Easy

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

    You may assume that the array does not change.
    There are many calls to sumRange function.

Subscribe to see which companies asked this question
*/

class NumArray { // 28ms
public:
    NumArray(vector<int> &nums) {
        int x = 0;
        for(auto a:nums){
            x += a;
            sum.push_back(x);
        }
    }

    int sumRange(int i, int j) {
        int left = i == 0? 0: sum[i-1];
        int right = sum[j];
        return right - left;
    }
private:
    vector<int> sum;
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);
class NumArray { // 30ms
public:
    NumArray(vector<int> &nums):sum(nums.size()) {
        int x = 0;
        for(int i = 0; i < nums.size(); i++){
            x += nums[i];
            sum[i] = x;
        }
    }

    int sumRange(int i, int j) {
        int left = i == 0? 0: sum[i-1];
        int right = sum[j];
        return right - left;
    }
private:
    vector<int> sum;
};
